package algorithms.sorts;

import algorithms.Utils;

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = Utils.randomArray(2011);
        //int[] arr = {1, 2, 5, 7, 4, 3, 6, 8, 9, 10, -9, -8};
        //bubbleSortFlag(arr);
        //bubbleSortPosition(arr);
        //bubbleSortTwoWayPosition(arr);
        //bubbleSortTwoWayPosition(arr);
//        System.out.println(Arrays.toString(arr));
//        bubbleSortPosition(arr);
        //   System.out.println(Arrays.toString(arr));
        System.out.println(Utils.isAscend(arr));
    }

    /**
     * 最原始的冒泡，另外一中写法是将最大值冒泡到右端
     */
    private static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = arr.length - 1; j > i; j--) {
                if (arr[j] < arr[j - 1]) {
                    Utils.swap(arr, j, j - 1);
                }
            }
        }
    }

    /**
     * 记录无交换标志，快速结束
     */
    private static void bubbleSortFlag(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            boolean swap = false;
            for (int j = arr.length - 1; j > i; j--) {
                if (arr[j] < arr[j - 1]) {
                    Utils.swap(arr, j, j - 1);
                    swap = true;
                }
            }
            if (!swap) break;
        }
    }

    /**
     * 记录最后交换位置，说明此位置之前整体有序，下一次只比较到此位置，
     * 最后交换位置变量为区间开始索引，经过一趟比较交换后，如果与区间开始索引相同则说明无交换，排序结束
     */
    private static void bubbleSortPosition(int[] arr) {
        int i = 0, pos = i;
        while (i < arr.length) {
            for (int j = arr.length - 1; j > i; j--) {
                if (arr[j] < arr[j - 1]) {
                    Utils.swap(arr, j, j - 1);
                    pos = j;
                }
            }
            if (pos == i) break;
            else i = pos;
        }
    }

    /**
     * 两路冒泡
     */
    private static void bubbleSortTwoWay(int[] arr) {
        int length = arr.length;

        for (int i = 0; i < length / 2; i++) {
            for (int j = length - i - 1; j > i; j--) {
                if (arr[j] < arr[j - 1]) {
                    Utils.swap(arr, j, j - 1);
                }
                int k = length - j - 1;
                if (arr[k] > arr[k + 1]) {
                    Utils.swap(arr, k, k + 1);
                }
            }
        }
    }


//    /**有问题
//     * 两路冒泡，两个方向都记录最后交换位置，缩小排序区间(趟数)
//     * 任何一路原理同bubbleSortPosition
//     * 标记法比较简单不再实现
//     */
//    private static void bubbleSortTwoWayPosition(int[] arr) {
//        int length = arr.length;
//        int start = 0;
//        int end = length - 1;
//        while (start < end) {
//            System.out.println(Arrays.toString(arr) + start + "," + end);
//            int j = end;
//            int oldStart = start;
//            int oldEnd = end;
//            for (; j > oldStart; j--) {
//                if (arr[j] < arr[j - 1]) {
//                    if (j - 1 == end || j == end) end++;
//                    Utils.swap(arr, j, j - 1);
//                    start = j;
//                }
//                int k = length - j - 1;
//                if (arr[k] > arr[k + 1]) {
//                    if (k + 1 == start || k == start) {
//                        start--;
//                    }
//                    Utils.swap(arr, k, k + 1);
//                    end = k;
//                }
//            }
//            if (oldStart == start) {
//                System.out.println(Arrays.toString(arr) + end + "," + end);
//                break;
//            }
//        }
//    }
}
